VLSI DSP之重定时

本节主要介绍了VLSI DSP中重定时的基本概念及其使用方法，包括割重定时与K倍降速。

重定时的基本概念

• 重定时（Retiming）：是一种变换技术，在不改变系统的输入输出特性的前提下，改变电路延迟元件的配置

• 延时单元可以在所有输出与所有输入之间移动：

  • 改变关键路径，从而提高时钟频率
  • 改变寄存器数量，从而能够减小面积
  • 不改变环路中的延迟
  • 不改变迭代边界

• 重定时后电路功能不变：

  $$ 左图:w(n)=ay(n-1)+by(n-2) $$

  $$
  y(n)=x(n)+w(n-1)=x(n)+ay(n-2)+by(n-3)
  $$

  $$
  右图:w_1(n)=ay(n-1)
  $$

  $$
  w_2(n)=by(n-2)
  $$

  $$
  y(n)=x(n)+w_1(n-1)+w_2(n-1)=x(n)+ay(n-2)+by(n-3)
  $$

---

重定时求解方法

1.割集重定时

• 若在一个方向的边上增加延时，则在另外方向的边上减少同样的延时

• 重定时前：关键路径为$T_M+T_A=3ut$，延时单元为4

• 重定时后：关键路径为$T_M+2T_A=4ut$，延时单元为5

2.节点重定时

• 重定时前：关键路径为$T_M+T_A=3ut$，延时单元为4

• 重定时后：关键路径为$T_M=2ut$，延时单元为5

3.重定时的数学求解

• 用有向图G表示电路：

  • 节点：表示算法中功能的执行，包含计算时间（数字）
  • 有向边：表示节点间通信关系
  • 权重：表示有向边的寄存器数
  

• 重定时值$r(v)$：
  $$
  r(v)=0 \Rightarrow 不操作
  $$

  $$
  r(v)>0 \Rightarrow 节点的每条输入边增加r(v)延时，同时节点的每条输出边减少r(v)延时
  $$

  $$
  r(v)<0 \Rightarrow 节点的每条输入边减少r(v)延时，同时节点的每条输出边增加r(v)延时
  $$

• 重定时方程：用来确定节点u到u—->v重定时后的权重
  $$
  w_r(e)=w(e)+r(v)-r(u),w_r(e)\ge0
  $$

  
  • $w(e)$为原始权重
  • $r(v)$为目的节点的重定时值
  • $r(u)$为原始节点的重定时值
  
  • 对于重定时的求解，需结合$w_r(e)\ge 0$以及设定多个目标，比如系统时钟周期和寄存器个数等，在此不等式方程组的约束条件下，搜索出使得规定目标最小化的解

4.K倍降速与割集重定时

• 首先用K个延时取代DFG中的每个延时，以产生DFG的K倍减速系统，然后对K倍减速的DFG进行割集重定时